#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 0  // undirected graph
#define vertex_max 4
#define edge_max   5
#endif

#if 0  // directed graph
#define vertex_max 3
#define edge_max   4
#endif

#if 1
#define vertex_max 5
#define edge_max   (8*2)
#endif

struct link
{
  int data;
  struct link * next;
};

struct graph
{
  struct link vertex[vertex_max + 1];
};

struct quan_link
{
  int data;
  int quan;
  struct quan_link * next;
};

struct quan_graph
{
  struct quan_link vertex[vertex_max + 1];
};

/* 无向图邻接表 */
void undirected_graph(struct graph * graph)
{
  int i, j, k;
  struct link * src;

  for (i = 1; i <= vertex_max; i++) {
    graph->vertex[i].data = i;
    graph->vertex[i].next = NULL;
  }

  for (k = 1; k <= edge_max; k++) {
    scanf("%d %d", &i, &j);
    //printf("%d %d\n", i, j);
    src = (struct link *) malloc (sizeof(struct link));
    src->data = j;
    src->next = graph->vertex[i].next;
    graph->vertex[i].next = src;

    src = (struct link *) malloc (sizeof(struct link));
    src->data = i;
    src->next = graph->vertex[j].next;
    graph->vertex[j].next = src;
  }
}

/* 有向图邻接表 */
void directed_graph(struct graph * graph) 
{
  int i, j, k;
  struct link * src;

  for (i = 1; i <= vertex_max; i++) {
    graph->vertex[i].data = i;
    graph->vertex[i].next = NULL;
  }

  for (k = 1; k <= edge_max; k++) {
    scanf("%d %d", &i, &j);
    src = (struct link *) malloc (sizeof(struct link));
    src->data = j;
    src->next = graph->vertex[i].next;
    graph->vertex[i].next = src;
  }
}

void mual(struct graph * graph)
{
  int i, j, k;
  struct link * src;

  for (i = 1; i <= vertex_max; i++) {
    graph->vertex[i].data = i;
    graph->vertex[i].next = NULL;
  }

  // 1
  src = (struct link *) malloc (sizeof(struct link));
  src->data = 4;
  src->next = graph->vertex[1].next;
  graph->vertex[1].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 2;
  src->next = graph->vertex[1].next;
  graph->vertex[1].next = src;

  // 2
  src = (struct link *) malloc (sizeof(struct link));
  src->data = 4;
  src->next = graph->vertex[2].next;
  graph->vertex[2].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 3;
  src->next = graph->vertex[2].next;
  graph->vertex[2].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 1;
  src->next = graph->vertex[2].next;
  graph->vertex[2].next = src;

  // 3
  src = (struct link *) malloc (sizeof(struct link));
  src->data = 4;
  src->next = graph->vertex[3].next;
  graph->vertex[3].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 2;
  src->next = graph->vertex[3].next;
  graph->vertex[3].next = src;

  // 4
  src = (struct link *) malloc (sizeof(struct link));
  src->data = 3;
  src->next = graph->vertex[4].next;
  graph->vertex[4].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 2;
  src->next = graph->vertex[4].next;
  graph->vertex[4].next = src;

  src = (struct link *) malloc (sizeof(struct link));
  src->data = 1;
  src->next = graph->vertex[4].next;
  graph->vertex[4].next = src;

}

void display(struct graph * graph)
{
  int i;
  struct link * src;

  for (i = 1; i <= vertex_max; i++) {
    src = graph->vertex[i].next;
    printf("vertex=%d: ", i);
    while (src != NULL) {
      printf(" %d ", src->data);
      src = src->next;
    }
    printf("\n");
  }
}

void undirected_quan_graph(struct quan_graph * graph)
{
  int i, j, k, quan;
  struct quan_link * src;

  for (i = 1; i <= vertex_max; i++) {
    graph->vertex[i].data = i;
    graph->vertex[i].quan = 0;
    graph->vertex[i].next = NULL;
  }

  for (k = 1; k <= edge_max; k++) {
    scanf("%d %d %d", &i, &j, &quan);

    src = (struct quan_link *) malloc (sizeof(struct quan_link));
    src->data = j;
    src->quan = quan;
    src->next = graph->vertex[i].next;
    graph->vertex[i].next = src;

    src = (struct quan_link *) malloc (sizeof(struct quan_link));
    src->data = i;
    src->quan = quan;
    src->next = graph->vertex[j].next;
    graph->vertex[j].next = src; 
  }
}

void directed_quan_graph(struct quan_graph * graph)
{
  int i, j, k, quan;
  struct quan_link * src;

  for (i = 1; i <= vertex_max; i++) {
    graph->vertex[i].data = i;
    graph->vertex[i].quan = 0;
    graph->vertex[i].next = NULL;
  }

  for (k = 1; k <= edge_max; k++) {
    scanf("%d %d %d", &i, &j, &quan);

    src = (struct quan_link *) malloc (sizeof(struct quan_link));
    src->data = j;
    src->quan = quan;
    src->next = graph->vertex[i].next;
    graph->vertex[i].next = src;
  }
}

int main()
{
  struct graph graph;
  struct quan_graph quan_graph;

#if 0
  undirected_graph(& graph);
  display(& graph);
#endif
#if 0
  //mual(& graph);
  display(& graph);
#endif
#if 1
  undirected_quan_graph(& quan_graph);
  display(& graph);
#endif

}
